class Node(object):
    """节点类"""

    def __init__(self, item):
        self.item = item
        self.lchild = None
        self.rchild = None


class BinaryTree(object):
    """完全二叉树"""

    def __init__(self, node=None):
        self.root = node

    def add(self, item):
        """添加节点"""

        if self.root == None:
            self.root = Node(item)
            return

        # 队列
        queue = []
        # 从尾部添加数据
        queue.append(self.root)

        while True:
            # 从头部取出数据
            node = queue.pop(0)
            # 判断左节点是否为空
            if node.lchild == None:
                node.lchild = Node(item)
                return
            else:
                queue.append(node.lchild)

            if node.rchild == None:
                node.rchild = Node(item)
                return
            else:
                queue.append(node.rchild)

    def breadh_travel(self):
        """广度优先遍历"""

        if self.root == None:
            return

        # 队列
        queue = []
        # 添加数据
        queue.append(self.root)

        while len(queue) > 0:
            # 取出数据
            node = queue.pop(0)
            print(node.item, end="")

            # 判断左右子节点是否为空
            if node.lchild is not None:
                queue.append(node.lchild)
            if node.rchild is not None:
                queue.append(node.rchild)

    def preorder_travel(self, root):
        """先序遍历 根 左 右"""
        if root is not None:
            print(root.item, end="")  # 根 ->
            self.preorder_travel(root.lchild)  # 左
            self.preorder_travel(root.rchild)  # 右

    def inorder_travel(self, root):
        """中序遍历 左 根 右"""
        if root is not None:  # 递归结束条件：递归至根为None。
            self.inorder_travel(root.lchild)  # 左 ->递归至最左 左为下层递归的根。下层无左节点时在下层执行下行代码即打印了左节点
            print(root.item, end="")  # 根 ->递归至最左的根
            self.inorder_travel(root.rchild)  # 右->递归至最左的右 右为下层递归的根。下层无左节点时执行在下层上行代码即打印了右节点

    def postorder_travel(self, root):
        """后序遍历  左 右 根"""
        if root is not None:
            self.postorder_travel(root.lchild)  # 左
            self.postorder_travel(root.rchild) # 右
            print(root.item, end="") # 根 # 左右都为下层的根，因此此处打印根，也即打印递归尽头的上层的左右，和本层的根



if __name__ == '__main__':
    tree = BinaryTree()
    tree.add("0")
    tree.add("1")
    tree.add("2")
    tree.add("3")
    tree.add("4")
    tree.add("5")
    tree.add("6")
    tree.add("7")
    tree.add("8")
    tree.add("9")
    tree.preorder_travel(tree.root)
    print()
    tree.inorder_travel(tree.root)
    print()
    tree.postorder_travel(tree.root)

"""
深度优先-先序遍历（根->左->右(递归形式)）
1. 左右都为下层的根，因此打印根，也即打印递归尽头的上层的左右，和本层的根
2. 左右根（注释标注的）代码的顺序，即先中后序遍历的顺序
"""
